#include<vector>
#include<algorithm>
using namespace std;
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if(nums.size()==1)return 1;
        //dp[i] 以i为结尾的摇摆序列的最大长度
        //[0]以i为结尾为呈上升趋势的最大长度 [1]下降趋势
        vector<vector<int>>dp(nums.size(),vector<int>(2,1));
        int ans=0;
        for(int i=1;i<nums.size();i++){
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]) dp[i][0]=max(dp[i][0],dp[j][1]+1);
                if(nums[i]<nums[j]) dp[i][1]=max(dp[i][1],dp[j][0]+1);
            }
            ans=max(ans,max(dp[i][0],dp[i][1]));
        }
        return ans;
    }
};
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if(nums.size()==1)return 1;
        //dp[i] 以i为结尾的摇摆序列的最大长度
        vector<int>dp(nums.size(),1);
        //趋势 -1 0 1
        vector<int>st(nums.size(),0);
        for(int i=1;i<nums.size();i++){
            for(int j=0;j<i;j++){
                int temp_dp=1;
                if(nums[i]==nums[j])
                    temp_dp=1;
                else{
                    if(st[j]==0&&nums[i]!=nums[j])
                        temp_dp=2;
                    else{
                        temp_dp=(st[j]>0?nums[i]<nums[j]:nums[i]>nums[j])?dp[j]+1:2;
                    }
                }
                if(temp_dp>dp[i]){
                    dp[i]=temp_dp;
                    st[i]=nums[i]==nums[j]?0:nums[i]>nums[j]?1:-1;
                }
            }
        }
        return *max_element(dp.begin(),dp.end());
    }
};